class code4 {
    int aim;
    List<Integer> path;
    List<List<Integer>> ret;
    public List<List<Integer>> combinationSum(int[] nums, int target) {
        path = new ArrayList<>();
        ret = new ArrayList<>();
        aim = target;

        dfs(nums,0,0);
        return ret;
    }
    public void dfs(int[] nums,int pos,int sum) {
        if(sum == aim) {
            ret.add(new ArrayList<>(path));
            return;
        }
        //剪枝
        if(sum > aim || pos == nums.length) return;

        for(int k=0; k*nums[pos] <= aim;k++) {
            if(k != 0) path.add(nums[pos]);
            dfs(nums,pos+1,sum+k*nums[pos]);
        }
        //全部完成后才能恢复现场
        for(int k=1;k*nums[pos] <= aim;k++) {
            path.remove(path.size()-1);
        }
    }
} 